{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 栈抽象数据类型及 Python 实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈(Stack)应该包含如下操作\n",
    "\n",
    "* `Stack()`: 创建一个空栈，不包含任何数据项\n",
    "* `push(item)`: 将 item 加入栈顶，并无返回值\n",
    "* `pop()`: 将栈顶数据项移除，并返回，栈被修改\n",
    "* `peek()`: 返回栈顶的数据，**但不移除，栈不被修改**\n",
    "* `isEmpty()`: 判断是否为空栈\n",
    "* `size()`: 返回栈中有多少个数据项"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用 *list* 来实现 ADT Stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1.将 list 的首端 (index=0) 作为栈顶"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self, item):\n",
    "        self.items.append(0, item)  # 时间复杂度 O(n)\n",
    "    \n",
    "    def pop(self):\n",
    "        return self.items.pop(0)    # 时间复杂度 O(n)\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[0]\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2.将 list 的末端 (index=-1) 作为栈顶"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "    \n",
    "    def pop(self):\n",
    "        return self.items.pop()     # 时间复杂度 O(1)\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[-1]       # 时间复杂度 O(1)\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "测试一个 Stack 实例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "s = Stack()\n",
    "\n",
    "print(s.isEmpty())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.push(4)\n",
    "s.push('dog')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dog\n"
     ]
    }
   ],
   "source": [
    "print(s.peek())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.push(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "print(s.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(s.isEmpty())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.push(8.4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.4\n"
     ]
    }
   ],
   "source": [
    "print(s.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(s.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "print(s.size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3.两种实现方法对比"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`index=-1` 的实现方法性能要大于 `index=0`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## 2 栈的应用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1.简单括号匹配"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
